import binaryresearchtree.BinarySearchTree;
import demo1.HashBuck;
import demo1.HashBuck2;
import jdk.internal.org.objectweb.asm.tree.analysis.Value;
import sun.reflect.generics.tree.Tree;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024-07-19
 * Time: 18:33
 */

class Student{
    public String id;
/*
* 自己写的类一定要去重写一下hashcode，equals方法
* 可以避免一些不必要的错误
* */
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }



    public Student(String id){
        this.id = id;
    }
}


public class Test {



    class Solution {
        public List<String> topKFrequent(String[] words, int k) {
            //第一步先把数组中的单词都放进map中并记录下key和val的值
            Map<String,Integer> map = new HashMap<>();
            //遍历数组
            for (String word : words){//for循环和foreach循环中的符号区别是要注意的：和；
                if (map.get(word) == null){
                    map.put(word,1);
                }else{
                    Integer value = map.get(word);
                    map.put(word,value+1);
                }
            }
            //第二步把map中元素放到小根堆中，PriorityQueue默认是小堆

            PriorityQueue<Map.Entry<String,Integer>> minHeap
                    = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
                //重写比较器，在实例化PriorityQueue的时候顺便new一下传入比较器参数
                @Override
                public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                    if (o1.getValue().compareTo(o2.getValue()) == 0){
                        return o2.getKey().compareTo(o1.getKey());
                    }//太离谱了，这一步绝杀关键因素，就是相同key的情况下，永达跟对的方式放，最后倒置的时候就可以还原，不写这一步，if(minHeap.size() < k)有问题

                    return o1.getValue().compareTo(o2.getValue());//返回值为正负零
                }
            });
            //遍历map.entrySet
            for (Map.Entry<String,Integer> entry : map.entrySet()){
                //放entry进顺序表也是有条件的
                if(minHeap.size() < k){
                    minHeap.offer(entry);//这里很重要，堆在offer的时候，建立的是大根堆还是小根堆取决于compare方法的条件，要理解底层代码
                }else {                //顺序表（小根堆）放满了

                    if (entry.getValue().compareTo(  minHeap.peek().getValue() ) > 0){    //要传入的那个entry（单词）的value值大于小根堆堆顶的value
                        minHeap.poll();
                        minHeap.offer(entry);
                    }else {
                        if(entry.getValue().compareTo(  minHeap.peek().getValue() ) == 0 ){
                            //很重要的一步：这里getValue相等了那么比较器的返回值不能是一个正负零的数而要是它们的key，所以在重写Compare方法的时候要再添加一种情况
                            if (  entry.getKey().compareTo(  minHeap.peek().getKey()  ) < 0){
                                minHeap.poll();
                                minHeap.offer(entry);
                            }
                        }
                    }
                }
            }

            //现在得到了一个（entry）小根堆，我们把小根堆放到顺序表里
            List<String> list = new ArrayList<>();
            for (int i = 0; i < k; i++) {
                Map.Entry<String,Integer> entry = minHeap.poll()  ;//让小根堆里的entry一个个出来添加到list顺序表里,注意添加进去的时候不要带value值
                list.add(entry.getKey());
            }
            //在倒置一下就是降序
            Collections.reverse(list);
            return list;
        }
    }




    public static void main9(String[] args) {
        //题2：统计每个数据存放的次数
        int[] array = new int[]{1,2,3,2,3,4,4,4};
        Map<Integer,Integer> map = new HashMap<>();
        //第一步把数据放进去
        for (Integer x : array){     //这个for循环的，循环变量x的设置很巧妙，x就是key
            if (map.get(x) == null){
                map.put(x,1);
            }else{
                Integer value = map.get(x);
                map.put(x,value+1);
            }
        }
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            System.out.println("key:"+entry.getKey()+"  " + "value:"+entry.getValue());
        }
    }

    public static void main8(String[] args) {
        //题1：去重
        int[] array = new int[]{1,2,3,3,4,4};
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            set.add(array[i]);
        }
        System.out.println(set);
    }

    public static void main7(String[] args) {


        //第一步：实例化Student类，
        Student student1 = new Student("1154932");
        Student student2 = new Student("115");
        Student student3 = new Student("11549322");

        //实例化hashBuck
        HashBuck2<Student,Integer> hashBuck2 = new HashBuck2<>();


        //放元素
        /*重点：
        * 在HashBuck2中put和getValue中hash的值，用hashCode时要么统一用自己重写过后的hashCode,要么统一用JDK自带的，最好用前者，
        **/
        hashBuck2.put(student2,2);
        Integer v = hashBuck2.getValue(student2);
        System.out.println(v);


        hashBuck2.put(student3,1);
        Integer vv = hashBuck2.getValue(student3);
        System.out.println(vv);


    }
    public static void main6(String[] args) {
        //因为map的put方法，（自己实现的是整型类型），有一个除法，用hashCode方法去转换
        //自己写的类都默认继承object类


        Student student1 = new Student("1154932194");
        Student student2 = new Student("1154932194");
        //理论上来说，id相同的student经过hashmap放进去之后，是同一个 位置，但是hashcode转化后的integer类型的数字不一样为什么？

        //把对象转换为具体的数值用hashCode方法，自己写的类没有这个方法，但是继承了object类。所以hashCode是object的
        System.out.println(student1.hashCode());// 用jdk自带的hashCode方法算出来的值是不一样的，那么x%len后，存放的地址也是不一样的
        System.out.println(student2.hashCode());


        System.out.println("测试一下自己写的hashcode");
        HashMap<Student,Integer> map2 = new HashMap<>();
        map2.put(student1,2);//用student1去放
        map2.get(student2);//用student2去取1的value


    }
    public static void main5(String[] args) {
        //第一步实例化HashMap
        HashMap<String,Integer> map = new HashMap<>();
        map.put("hahaha",2);
        map.put("dsadsa",3);
        map.put("jiayou",5);

        //第二步：获取key=“hahaha” 所对应的value
        Integer val = map.get("hahaha");
        System.out.println(val);

        //第三步
        System.out.println("打印一下map");//打印结果是一个集合
        System.out.println(map);

        //第四步：要实现遍历map，把map转换成set,因为set实现了iterable接口，才能实现迭代器遍历
        System.out.println("遍历map");
        for(Map.Entry<String,Integer> entry : map.entrySet()){  // map.entrySet返回的类型是KV的映射关系，可以看为一个整体，所以返回类型就是MAP.Entry<K,V>
            System.out.println("Key:"+entry.getKey() + "  " + "Value:"+entry.getValue());
        }


        //第五步：不能用TreeMap，因为TreeMap在放入的时候要进行比较，很明显Student类型不能进行相互比较
        HashMap<Student,Integer> map2 = new HashMap<>();
        map2.put(new Student("lzh"),2);//放的类型可以根据自己创建的类，进行变化
        map2.put(new Student("lzh"),3);
        map2.put(null,4);//可以放null

        //第六步：（区别）Set只存kay，HashSet 方法底层是HashMap，每次存储的时候(E,PRESENT)默认的value就是一个object对象
        /*Set中不能存储相同的key*/
        HashSet<String> set = new HashSet<>();
        set.add("hello");
        set.add("zlh");
        set.add("key");
        set.add("hello");
        System.out.println(set);//set以数组的形式打印出来，无序的，并且会自动过滤重复的数据
    }



    public static void main4(String[] args) {
        HashBuck hashBuck = new HashBuck();
        hashBuck.put(1,2);
        hashBuck.put(2,3);
        hashBuck.put(3,4);
        hashBuck.put(4,5);
        System.out.println(hashBuck.get(3));

    }


    public static void main3(String[] args) {
        Set<String> set = new TreeSet<>();
        set.add("hello");
        set.add("zlh");
        set.add("key");
        set.add("hello");
        set.add("hello");
        System.out.println(set);//打印结果是无序的，set是只存key的
        Iterator<String> it = set.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }

    }





    public static void main2(String[] args) {
        TreeMap<String, Integer> map1 = new TreeMap<>(); //Map只能实例化TreeMap和HashMap，Map只是一个接口
        //TreeMap是实现了Map的接口  这里为了方便看源码用TreeMap了
        map1.put("hahaha",5);
        map1.put("dsadsa",6);
        map1.put("jiayou",7);

        Integer val1 = map1.get("hahaha");
        System.out.println(val1);//通过key获取val值

        Integer val2  = map1.getOrDefault("dwqdqw",88);
        System.out.println(val2);//结果为88

        /*获取所有的key
        * 顺序是乱的*/
        Set<String> set = map1.keySet();
        System.out.println(set);

        /*获取所有的val*/
        Collection<Integer> collection = map1.values();
        System.out.println(collection);
        System.out.println("======================");


        /*Map是一个接口
        * Set的每一个元素就是map的entry*/
        Set<Map.Entry<String,Integer>> entrySet = map1.entrySet();
        for (Map.Entry<String,Integer> entry : entrySet ){     //遍历entryset，entrySet是一个集合 ， 遍历的是节点，
            System.out.println("key:" + entry.getKey() + "  val:" + entry.getValue());
        }



        System.out.println("========================");

    }



    public static void main1(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        int[] array = new int[]{5, 12, 3, 11, 15};
        for (int i = 0; i < array.length; i++) {
            binarySearchTree.insert(array[i]);
        }

        System.out.println(binarySearchTree.search(5));
        binarySearchTree.remove(11);
        System.out.println(binarySearchTree.search(11));

    }
}
